% -*- mode:     LaTeX -*- -------------------------------------------------- %
% File:         Zebu_intro.tex
% Description:  Introduction to the reversible grammar formalism
% Author:       Joachim H. Laubsch
% Created:      27-May-92
% Modified:     Mon Apr 11 14:03:16 1994 (Joachim H. Laubsch)
% Language:     LaTeX
% Package:      USER
% Status:       Experimental (Do Not Distribute) 
% RCS $Header: $
%
% (c) Copyright 1992, Hewlett-Packard Company
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Revisions:
% RCS $Log: $
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\documentstyle{article}    % Specifies the document style.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\alt}[0]{$\dot{|}\: $}
\newcommand{\metavar}[1]{\mbox{$\langle\/$#1$\/\rangle$}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{{\sf Zebu}: A Tool for Specifying Reversible LALR(1) Parsers}
\author{Joachim Laubsch (laubsch@hplabs.hp.com)}    

\begin{document}

\maketitle
\bibliographystyle{plain}

\begin{abstract}
{\sf Zebu}\footnote{``{\bf zebu}{\em n}., {\em pl}. {\bf -bus}, {\bf
-bu}: 1. an oxlike domestic animal ({\em Bos indicus}) native to Asia
and parts of Africa: it has a large hump over the shoulders, short,
curving horns, pendulous ears, and a large dewlap and is resistant to
heat and insect-born deseases.''  [Webster's New World Dictionary.]
A zebu should not be confused with a yacc or a gnu although it bears
similarity to each of them.} is part of a set of tools for the
translation of formal languages.  {\sf Zebu} contains a LALR(1) parser
generator like Yacc does.  Aside from generating a parser, {\sf Zebu}
will also generate the inverse of a parser (unparser).  In contrast to
Yacc, the semantics is not given in terms of ``routines'' but
declaratively in terms of typed feature structures.

The ability to declaratively define a reversible grammar, together with
a rewrite-rule mechanism ({\sf Zebu-RR}) for transforming abstract syntax
trees constitute the basic tools for specifying translators for formal
languages.

\paragraph{Keywords} Formal language, LALR-grammar, parsing, translation,
generation, interoperability, LEX, YACC.

\end{abstract}

\section{Introduction}
Our goal is to develop an environment for the design, analysis and
manipulation of formal languages, such as programming languages,
markup languages, data interchange formats or knowledge representation
languages (such as the translation to and from KIF) \cite{cs:kif92}.
Being able to design, analyze, and manipulate formal languages is
crucial for achieving software interoperability
\cite{cs:Genesereth92}, automatic code analysis, indexing, and
retrieval for potential reuse.  Zebu has been applied to writing
translators for formal languages \cite{ap:refine}.  The main idea of
this work is that a module $m$ communicates by sending or receiving
messages in some language $L(m)$, and that for various reasons
different modules use different languages.  For communication to be
successful, translators have to be used.  {\sf Zebu} provides tools to
define translators at a high level of abstraction\footnote{The
rewrite-rule mechanism (Zebu-RR) is implemented, and will be
described in a future report.}.


McCarthy introduced the notion of ``abstract'' and ``concrete''
syntax.  The concrete syntax describes the surface form of a
linguistic expression, while the abstract syntax describes a
(composite) object. E.g. ``1+a'' is the surface string rendered by a
particular concrete syntax for an object described by an abstract
syntax: an addition operation with two operands, the first being the
numeral ``1'', and the second being the variable named ``a''.

Manipulation of linguistic expressions is much easier to express in
the abstract syntax than in the concrete syntax.  

If we were to design an algorithm for simplifying expressions of some
language --- say ``arithmetic'' --- we would use as the front end the
``arithmetic-parser'' to translate into abstract syntax, then express
the simplification rules in terms of tree transformation rules that
operate on the abstract syntax, and finally add as the back-end the
``arithmetic-unparser''.

More generallly, if we were to design an algorithm for translating
from language A to language B, we would define reversible grammars for
languages A and B, and sets of rewrite rules to transform the abstract
syntax trees from the domain of language A to the domain of language
B.  The front end would be the ``A-parser'' and the back-end the
``B-unparser''

The work described in this report ows a lot to the pioneering research
at Kestrel \cite{ap:smith85} that resulted in the {\sf
Refine}\footnote{{\sf Refine} is a trademark of Reasoning Systems,
Palo Alto.} program transformation system \cite{refine}.  The basic
ideas underlying {\sf Zebu} are already present in {\sf Refine}.  {\sf
Zebu} is a much more compact sytem than Refine (it runs on a MacIntosh
in MacIntosh Common Lisp), and the semantics is expressed in typed
feature structures.  {\sf Zebu} also offers the possibility of
defining a meta-grammar.  {\sf Zebu} lacks {\sf Refine}'s ability to
declaratively specify transformations using a pattern language.
\footnote{{\sf Zebu} can be obtained via anonymous ftp from
hplabsz.hpl.hp.com (15.0.152.161) as a compressed tar file:
pub/zebu-???.tar.gz.  It contains several example grammar definitions.}

The LALR(1) parsing table generated by {\sf Zebu} follows algorithms
described in \cite{aho:79} or \cite{compiler:88}. The current
implementation was developed from the {\sf Scheme} program developed by
William Wells and is written in {\sf Common Lisp}.

The next section will explain how a grammar can be defined, and how
semantics can be associated with a grammar rule. Section \ref{Options}
describes the definition of the semantic domain.  With this capability
it is possible to state declaratively what the abstract syntax should
look like. Section \ref{meta-grammar} describes a simpler grammar
notation that is very close to ordinary BNF.  Section \ref{Compiler}
summarizes the functional interface of Zebu and explains how a parser
can be customized.  The last chapter describes, how lexical analysis
can be defined using regular expressions and parameterization.


\section{The Representations of Grammars in Files}

\subsection{Grammar notation}

We first describe the null-grammar, which is a powerfull but verbose
way to specify a grammar.  Only a parser and optionally a domain will
be generated but an unparser (printer) will not.  If this is desired,
you must use the notation of the meta-grammar "zebu-mg" which is
described in section \ref{meta-grammar}.

Non-terminals are represented by symbols, terminals (also referred to
as keywords) by strings.  There are the following open classes of
non-terminals\footnote{The Kleene * indicates 0 or more occurences of
the preceding constituent}:

\begin{tabbing}
mm\=mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm\kill
  \> {\tt identifier}  \= ::= \metavar{lisp symbol} \\
  \> {\tt number}      \> ::= \metavar{integer} \\
  \> {\tt keyword}     \> ::= \metavar{string} \\
where\\
  \>\metavar{integer} ::= \metavar{digit}* \\
  \>\metavar{string} ::= " \metavar{character}* "
\end{tabbing}

A \metavar{lisp symbol} may be qualified by a package name, e.g. {\tt
zb:cons-1-3} is a valid identifier.  In case packages should be
disallowed during lexical analysis, the variable {\tt
*disallow-packages*} should be bound to {\em true}.  (It defaults to
{\em false}).  The alphabetic case of a keyword is not significant if
the variable {\tt zb:*case-sensitive*} is {\em false} (the default)
when the grammar is loaded.

If alphabetic case of identifiers is to be preserved, {\tt
zb:*preserve-case*} should be set to {\em true}.  Other
categories can be defined as regular expressions (see \ref{lex-cats}). 


\subsubsection{Grammar Rules}

\paragraph{Grammar Rule Syntax}

A grammar file consists of a header (the ``options list'', see section
\ref{grammar-options}) followed by one or more domain definitions or
grammar rules.  The non-terminal defined by the first grammar rule is
also the {\em start-symbol} of the grammar.  A parser will accept
exactly the strings that rewrite to the {\em start-symbol}.

This example shows how a BNF-like rule can be encoded as a {\sf Zebu}
grammar rule (using the null-grammar):
\begin{quote}
 A ::= B $|$ C \metavar{number} $|$ ``foo'' A $|$ ``c'' $|$ \metavar{the-empty-string} 
\end{quote}

{\tt \begin{tabbing}
mmmmmmmmm\=mmmmmmmmmmmmmmmmmmmmmmmmmmmmm\=\kill
(defrule \>A                            \\
         \> := B                        \>; (1)\\
         \> := (C NUMBER)               \>; (2)\\
         \> := ("foo" A)                \>; (3)\\
         \> := "c"                      \>; (4)\\
         \> := ()                       \>; (5)\\
         \>)
     \end{tabbing}}

This rule describes 5 productions, all deriving the non-terminal {\tt
A}.  Each of the productions has the left-hand side {\tt A}. The
right-hand side of (1) consists of just one constituent, the
non-terminal {\tt B}. (2) has a right-hand of length 2, and its second
constituent is the non-terminal {\tt NUMBER} (which rewrites to any
integer, real or rational). (3) is a recursive production.  (4)
contains just the terminal (or keyword) {\tt "c"}. (5) derives the
empty string.

None of these productions has a semantic action attached.  By default,
the semantic action is the {\tt identity} function if the right-hand
side of the rule consists of a single constituent and the {\tt
identity*} function otherwise.  ({\tt identity*} is defined as the
function that returns all its arguments as a list.)

\paragraph{Grammar Rule Semantic Actions}

If we want to attach other than these default semantic actions, we have to
use a {\tt :build} clause after a production.

The build clause has the syntax:

\begin{tabbing}
mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm\kill
 \metavar{build clause} ::= \={\tt :build} (\metavar{lisp function} \metavar{argument list})\\
 \metavar{build clause} ::= \>{\tt :build} \metavar{atomic lisp form}\\
 \metavar{build clause} ::= \>{\tt :build} ({\tt :form} \metavar{lisp form})\\
 \metavar{build clause} ::= \={\tt :build} (\={\tt :type} \= \metavar{struct-type}\\
                            \>              \>{\tt :map}  \> ((\metavar{non-terminal} . \metavar{Slot}) ...))
\end{tabbing}

The first case 
\begin{quote}
 {\tt :build} (\metavar{lisp function} \metavar{argument list})
\end{quote}

is like a function call.  It may contain free variable occurrences.
These will be bound to the non-terminal constituents of the same name
occuring in the right-hand side of the production at the time of
applying the semantic action.

In the second case
\begin{quote}
        {\tt :build} \metavar{atomic lisp form}
\end{quote}

the \metavar{atomic lisp form} must be a function.  It will be applied to the
constituents of the right-hand side.  This function should have the same
number of arguments as the right-hand side of the corresponding
production has constituents.

Since it happens often, that only some of the constituents of the
right-hand side are selected, or combined, a few useful semantic actions
have been predefined in {\sf Zebu}.\footnote{They are described in the file
"zebu-actions.l".} 

An example for such a predefined action is the function {\tt cons-2-3}
which takes 3 arguments and returns a {\em cons} of its second and
third argument.

The third form of the {\tt :build} clause is just a long way to write
the first form, i.e.
\begin{quote}
 {\tt :build} (\metavar{lisp function} \metavar{argument list})
\end{quote}

 is the same as
\begin{quote}
 {\tt :build}  ({\tt :form} (\metavar{lisp function} \metavar{argument list}))
\end{quote}

Similarly,

\begin{quote}
 {\tt :build} (progn \metavar{atomic lisp form})
\end{quote}

 is the same as

\begin{quote}
 {\tt :build} ({\tt :form} \metavar{atomic lisp form})
\end{quote}

The last {\tt :build} clause is more interesting:
\begin{tabbing}
mmmmmm\=mmmmmmmmmmmmmmmmmmmmmmmmmmmmmm\kill
      \>{\tt :build}  (\={\tt :type} \= \metavar{struct-type}\\
      \>               \>{\tt :map}  \>((\metavar{Nonterminal} . \metavar{Slot}) ...))
\end{tabbing}

where \metavar{struct-type} is a symbol that must be the name of a
structure type.  Instead of having to write the semantic action as a
constructing form, we just have to specify the type and the mapping of
non-terminals to slots, as in the following example\footnote{(taken
from the grammar named ``pc1''; see the file ``pc1.zb'' in the test
directory)}:

{\tt \begin{tabbing}
mmmmmmmmm\=mmmmmmmmmmmmmmmmmmmmmmmmmmmmm\=\kill
(defrule Boolean-Expr\\
  \> :=     (Formula.1 "and" Formula.2)\\
  \> :build (\=:type Boolean-And \\
  \>         \>:map (\=(Formula.1 . :-rand1) \\
  \>         \>      \>(Formula.2 . :-rand2))) \\
\\
  \> := (Formula.1 "or" Formula.2) \\
  \> :build (:type Boolean-Or \\
  \>         \>:map ((Formula.1 . :-rand1) \\
  \>         \>      \>(Formula.2 . :-rand2))) \\
  \>)
     \end{tabbing}}

The map indicates that the slot {\tt -rand1} is to be filled by the
value of the non-terminal {\tt Formula.1}, etc.

This example also makes use of the {\tt ".n"} notation: If on the
right-hand side of a production a nonterminal occurs repeatedly, we
distinguish it by appending {\tt "."} and a digit.

The function {\tt print-actions} applied to the name of a grammar may
be used to find out what the generated code for the semantic actions
looks like, e.g. after compiling the sample grammar {\tt ``pc1.zb''}:

{\tt \begin{verbatim}
(print-actions "pc1")

...
Rule: BOOLEAN-EXPR
(LAMBDA (FORMULA.1 DUMMY FORMULA.2)
        (DECLARE (IGNORE DUMMY))
        (MAKE-BOOLEAN-AND :-RAND1 FORMULA.1 :-RAND2 FORMULA.2))
(LAMBDA (FORMULA.1 DUMMY FORMULA.2)
        (DECLARE (IGNORE DUMMY))
        (MAKE-BOOLEAN-OR :-RAND1 FORMULA.1 :-RAND2 FORMULA.2))
...
\end{verbatim}}

These semantic actions have been generated from the {\tt :build}
clauses of the above rule for {\tt Boolean-Expr}.

\section {The Options List of the Grammar File} \label{Options}

\subsection{Keyword Arguments to Grammar Construction}
\label{grammar-options}

Some global information to control grammar compilation, lexical
analysis, and the generation of semantic actions will be declared in
the beginning of a grammar file\footnote{A grammar file has the
default type ".zb".}.  We chose to let the first list of a grammar
file take the form of a keyword argument list to be given to the
function {\tt zb:make-grammar}.  The following keywords are valid:

\begin{tabbing}
mmmmmmmmmmmmmmmmmm\=mmmmmmmmmmmmmmmmmmmm\kill
 {\tt :name} \> a string, the name of the grammar\\
\\
 {\tt :package} \> a string, the name of the package where the\\
                \> non-terminal symbols and the function symbols \\
                \> used in semantic actions reside \\
\\
 {\tt :identifier-start-chars} \> a string.  During lexical analysis any\\
              \> character in this string can start an {\tt identifier} \\
              \> non-terminal. \\
              \> The default is {\tt *identifier-start-chars*}.\\
\\
 {\tt :identifier-continue-chars} \> a string. During lexical analysis any\\
                \> character in this string can continue an \\
                \> {\tt identifier} (i.e. characters not in this string  \\
                \> terminate {\tt identifier}). The default is \\
                \> {\tt *identifier-continue-chars*}.
\\      
 {\tt :string-delimiter} \> a character, the character that delimits a\\
                \> string to be represented as a {\sf Common Lisp} string. \\
                \> (default \verb+#\"+) \\
\\
 {\tt :symbol-delimiter} \> a character, the character that delimits a\\
                \> string to be represented as a {\sf Common Lisp} symbol.\\
                \> (default \verb+#\'+) \\
\\
 {\tt :domain} \> a list, representing the hierarchy of the domain.\\
                \>  See section \ref{domain} below. \\
\\
 {\tt :domain-file} \> a string naming the file where the generated CL\\
                \> program that implements the domain will be stored. \\
                \> Definitions of functions for semantic actions and\\
                \> regular expression categories are kept here as well. \\
                \> This string defaults to the concatenation of the\\
                \> grammar's :name and ``-domain''.\\

\\
 {\tt :grammar} \> a string, by default: {\tt "null-grammar"}, naming
the \\
                \> grammar to be used to parse the grammar defined \\
                \> in this file.  If the grammar {\tt "zebu-mg"} is used, \\
                \> an unparser will also be generated. \\
\\
 {\tt :lex-cats} \> an association list of terminal category names and \\
                \> regular expressions (see section \ref{lex-cats}) \\
\\
 {\tt :white-space} \> a list of characters each of which will be ignored \\
                \> before a token. (default \verb+(#\Space #\Newline
                #\Tab)+)
\\
 {\tt :case-sensitive} \> true if the case of keywords is significant, \\
               \> false otherwise (default \em{false}).

\end{tabbing}


\subsection{Defining a Domain} \label{domain}

The {\tt :domain} keyword is used to specify a type hierarchy. This
specification will expand into {\tt defstruct} forms that implement
this hierarchy.  It is also possible to write such structure
definitions directly into the grammar file.  The value of the {\tt
:domain} keyword argument must be a list of the following form:
\begin{tabbing}
mm\=\=mmmmmmmmmmmmmmmmmmm\kill
  \>(\metavar{Root Struct} \\
  \>\>{\tt :subtype} \metavar{Struct Desc} \\
  \>\>{\tt :subtype} \metavar{Struct Desc} \\
  \>\> ...) \\
\\
  \>\metavar{Root Struct} ::= \metavar{Symbol} \\
\\
mm\=mmmmmmmmmmmmmmmmmmm\kill
  \>\metavar{Struct Desc} ::= \= \metavar{Symbol} $|$ \\
  \> \>( \metavar{Symbol} {\tt :slots} (\metavar{Slot} ...) ) $|$ \\
  \> \>( \metavar{Symbol} \= {\tt :slots} (\metavar{Slot} ...) \\
  \> \>                   \> {\tt :subtype} \metavar{Struct Desc} \\
  \> \>                   \> {\tt :subtype} \metavar{Struct Desc} \\
  \> \> ... )\\
\\
  \> \metavar{Slot} ::= \metavar{Symbol} $|$ ( \metavar{Slot Name} 
\metavar{Filler Type} ) \\
  \> \metavar{Filler Type} ::= \metavar{Symbol}
\end{tabbing}

This describes a type hierarchy with root node \metavar{Root Struct}.
A node of the hierarchy tree can have children, denoted by {\tt
:subtype} followed by the structure description of the child node.
Each node can have slots, described as a list following {\tt :slots}.
A child node inherits the slots of its parent node.  The value of a
slot can be type-restricted to \metavar{Filler Type}.

\metavar{Root Struct} will be implemented as a structure type directly
below the structure type {\tt kb-domain}, i.e. ({\tt kb-domain-p} x)
is {\em true} for any instance x of a subtype of \metavar{Root Struct}.

\paragraph{Example domain definition}
\label{pc2}
The grammar defined in ``pc2.zb'' accepts a simple propositional
calculus language with sentences such as
\begin{quote}
        {\tt walks(agent: John)},
\end{quote} 
which yields the following abstract syntax (printed out using the
{\sf Common Lisp} structure printer):

{\samepage \tt \begin{tabbing}
mm\=mmmmm\kill
  \>\#S(ATOMIC-WFF \=-PREDICATE WALKS \\
  \>               \>-ROLE-ARGUMENT-PAIRS \#S(\=ROLE-ARGUMENT-PAIR\\
  \>               \>                         \>-ROLE AGENT\\
  \>               \>                         \>-ARGUMENT JOHN) )
     \end{tabbing}
}

The types --- such as {\tt ATOMIC-WFF} and {\tt ROLE-ARGUMENT-PAIR}
--- are defined by the following domain declaration:

{\tt \begin{tabbing}
mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm\kill
 :domain (\=PC ;; PC is the root of the hierarchy\\
          \>:subtype (\=Formula \\
          \>          \>:subtype (Propositional-variable :slots (-name)) \\
          \>          \>:subtype \=(Boolean-Expr \\
          \>          \>         \> :slots (\=(-rand1    Formula) \\
          \>          \>         \>         \>(-rand2    Formula)) \\
          \>          \>         \>:subtype Boolean-Or \\
          \>          \>         \>:subtype Boolean-And)) \\
          \>:subtype (Boolean-Op :slots (-name)) \\
mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm\kill
          \>:subtype (\=Atomic-Wff \\
          \>          \>:slots (\=-predicate\\
          \>          \>        \>(-Role-Argument-Pairs Sequence))) \\
          \>:subtype (Role-Argument-Pair :slots (-Role -Argument)) \\
          \>)
\end{tabbing}}

\section{The {\sf Zebu} Meta Grammar} \label{meta-grammar}

Using the grammar "zebu-mg" as the {\tt :grammar} argument in the
options list indicates that the following grammar is to be
preprocessed with the grammar ``zebu-mg'' before compilation.

The advantages of the meta-grammar (versus the default null-grammar)
are a more concise representation of rules, automatic generation of
the functions that implement the semantic actions and reversibility of
the grammar (generation of printing functions).

The disadvantage is that the semantics is limited to constructing
typed feature structures.  But these have great expressive power, and
furthermore could subsequently be transformed into some other program.
Typed feature structures are ideally suited to present abstract
syntax.  The fact that unification, specialization and generalization
are well defined operations on feature structures, makes them
appropriate for further transformations by ({\sf Zebu-RR}).  For an
introduction into feature structures see \cite{johnson:88}.

Since there is a restricted way of expressing the semantics of a rule --
namely as a typed feature structure -- the grammar compiler will be able to
generate code for the domain hierarchy and print-functions associated with
each type of that domain.

"zebu-mg" is defined in terms of the null-grammar described
above\footnote{You may study the definition of the meta grammar in
terms of the null-grammar in the file "zebu-mg.zb".}.

\paragraph {BNF description of ``zebu-mg'':}
\begin{tabbing}
mmm\=mmmmmmmmmmmm\=mmmmmmmmmmmmmmmmmmm\kill
 \>\metavar{Domain-Defn} \> ::= \= \metavar{Type-name} \verb+":="+
\metavar{Feat-Term} \\
 \> \> \>[ \verb+"<<"+ "print-function:" Identifier \verb+">>"+ ] {\tt ";"}\\
 \>\metavar{zb-rule}     \> ::= \metavar{Non-terminal} \verb+"-->"+
\metavar{Rhs} {\tt ";"}\\
 \>\metavar{Rhs}         \> ::= \metavar{Rhs1} \metavar{More-Rhs} $|$ \metavar{Kleene-Rhs}\\
 \>\metavar{Rhs1}        \> ::= \metavar{Constituent}* [ {\tt "\{"}
\metavar{Semantics} {\tt "\}"} ]\\
 \>\metavar{Constituent} \> ::= \metavar{Identifier} $|$ \metavar{String}\\
 \>\metavar{More-Rhs}    \> ::= $|$ \metavar{Rhs1} \metavar{More-Rhs}\\
 \>\metavar{Semantics}   \> ::= \metavar{Feat-Term}\\
\end{tabbing}


A \metavar{Feat-Term} is a typed attribute value matrix.
\begin{tabbing}
mmm\=mmmmmmmmmmmm\=mmmmmmmmmmmmmmmmmmm\kill
 \>\metavar{Feat-Term}      \> ::= [\metavar{Type-name} ":"] \metavar{Conj}\\
 \>\metavar{Conj}           \> ::= {\tt "["} \metavar{Label-value-pair} * {\tt "]"}\\
 \>\metavar{Label-value-pair} \> ::= {\tt "("} \metavar{Identifier}
\metavar{Feat-Term} {\tt ")"} \\
 \>\metavar{Type-name} \> ::= \metavar{Identifier}
\end{tabbing}


This BNF-notation makes use of
\begin{enumerate}
  \item star (*) for 0 or more repetitions of the preceding constituent
  \item bar ($|$) for alternation
  \item brackets ([]) for marking the enclosed constituents as optional
  \item a quotation symbol (") for delimiting keywords        
\end{enumerate}

The above definition is somewhat oversimplified, since it does not
deal with the ".n" notation for \metavar{Constituent}: if on the
right-hand side of a production a non-terminal occurs repeatedly, we
can distinguish it by appending "." and a digit to the identifier.
The semantics can then unambiguously refer to this identifier.

The semantics is described as a typed feature structure.  Names of
variables occuring in feature term position corespond to constituent
names in the right-hand side of the rule.  The effect of applying a
rule is to instantiate a feature structure of the type described in
the rule semantics, substituting variables with their values.

If the relation between semantics and syntax is one-to-one, the inverse of
a parser, a printer, can be generated.

\subsection {Domain Definition}

Although it is possible to specify the hierarchy of domain types using
the {\tt :domain} keyword as in section \ref{domain}, a more
convenoient syntax is offered by the meta grammar rule
\metavar{Domain-Defn}.

The type definition
\begin{quote}
{\it atype} := {\it super}: [({\it $s_1$}) ... ({\it $s_n$})];
\end{quote}
will define the type {\it atype} inheriting from {\it super}, and
having slots {\it $s_1$} through {\it $s_n$}.

\begin{quote}
{\it atype} := [({\it $s_1$}) ... ({\it $s_n$})];
\end{quote}
is as above but defines the type {\it atype} as a subtype of the
top type named {\tt KB-domain}.

A slot may be type restricted as in:
\begin{quote}
{\it atype} := {\it super}: [({\it $s_1$} {\tt KB-sequence})];
\end{quote}
which restricts {\it $s_1$} to be of type {\tt KB-sequence}.  An
optional {\it print-function} may be specified, as in
\begin{quote}
{\it atype} := {\it super}: [({\it $s_1$})]
 \verb+<<+ {\tt print-function:} {\it print-atype} \verb+>>+;
\end{quote}
Here we supply for {\it atype} its own printer called {\it
print-atype} and no printer will be generated for {\it atype}.

\subsection {Example Grammars}

\paragraph {Example Grammar for Arithmetic Expressions}

{\tt \begin{verbatim}
(:name "arith-exp" :grammar "zebu-mg")

;; Domain definition

Arith-exp := Kb-domain: [];
Factor    := Arith-exp: [(-value)] <<print-function: Print-factor>>;
Mult-op   := Arith-exp: [(-arg1) (-arg2)];
Plus-op   := Arith-exp: [(-arg1) (-arg2)];

;; Productions

EE -->  EE "+" TT { +-op: [(-arg1 EE) (-arg2 TT)] }
        |  TT ;

TT --> TT "*" F   { *-op: [(-arg1 TT) (-arg2 F)] }
       | F ;

F -->  "(" EE ")"        { factor: [(-value EE)] }
       | IDENTIFIER      { factor: [(-value IDENTIFIER)] }
       | NUMBER          { factor: [(-value NUMBER)] } ;

\end{verbatim}}

The semantics of the first rule says that an object of type {\tt +-op}
should be created with slot {\tt -arg1} filled with the value of {\tt
EE} and {\tt -arg2} filled with the value of {\tt TT}.

\paragraph {Example Grammar for Propositional Calculus}

This grammar defines the same domain as above (\ref{pc2}).  Compiling
it generates a parser and a generator. 

{\tt \begin{verbatim}

(:name "pc2"
 :package "CL-USER"
 :grammar "zebu-mg")

;; Domain definition

Formula := kb-domain: [];

 Propositional-variable := Formula: [(-name) ];
 P-Formula              := Formula: [(-content) ];
 Boolean-Expr           := Formula: [(-rand1 Formula) (-rand2 Formula)];
    Boolean-Or          := Boolean-Expr: [];
    Boolean-And         := Boolean-Expr: [];
 Atomic-Wff             := Formula: [(-predicate)
                                     (-Role-Argument-Pairs RAP-list)];

Role-Argument-Pair := kb-domain: [(-Role) (-Argument)];

RAP-list := kb-domain: [(-first) (-rest)];
  RAP-empty-list := RAP-list:[];

;; Productions

Formula --> Propositional-variable
            | Boolean-Expr
            | "(" Formula ")" {P-Formula:[(-content Formula)]}
            | Atomic-Wff;  

Propositional-Variable
  --> Identifier {Propositional-variable: [(-name Identifier)]};

Boolean-Expr --> Formula.1 "and" Formula.2
                 {Boolean-And: [(-rand1 Formula.1)
                                (-rand2 Formula.2)]}

                | Formula.1 "or" Formula.2
                  {Boolean-Or: [(-rand1 Formula.1)
                                (-rand2 Formula.2)]};

Atomic-Wff --> Identifier "(" Role-Argument-Pairs ")"
               { Atomic-Wff:
                 [(-predicate Identifier)
                  (-Role-Argument-Pairs Role-Argument-Pairs)]};

Role-Argument-Pairs -->
      { RAP-empty-list: [] }
      | Role-Argument-Pair Role-Argument-Pairs
        { RAP-list: [(-first Role-Argument-Pair)
                     (-rest  Role-Argument-Pairs)]};

Role-Argument-Pair --> 
      Identifier ":" Term
      {Role-Argument-Pair: [(-Role Identifier)
                            (-Argument Term)]};

Term -->  Identifier | Number ;
     \end{verbatim}
}

\subsection {The Kleene * Notation}

The meta-grammar ``zebu-mg'' provides an abbreviated notation for
repeated occurrences of a non-terminal, separated by a keyword.  The
syntax for this is:

\begin{tabbing}
mmmm\=mmmmmmmmm\=mmmmmmmmmmmmmmmmmmmmmmmmmmm\=\kill
 \>\metavar{Kleene-Rhs} \> ::= \metavar{Identifier} {\tt *} \metavar{String} \>(1)\\
 \>\metavar{Kleene-Rhs} \> ::= \metavar{Identifier} {\tt +} \metavar{String} \>(2)\\
\end{tabbing}

The meaning of (1) is that 0 or more occurrences of the constituent
named by \metavar{Identifier} and separated by \metavar{String} will
be accepted by this rule, and that the sequence of the results of
these constituents will be returned as the semantics of
\metavar{Kleene-Rhs}.  The meaning of (2) is the same, except that at
least one occurrence of the constituent has to be found.

The semantics of a \metavar{Kleene-Rhs} production is an implicit
sequence construction. The Kleene-constituent (\metavar{Identifier}
concatetenated with {\tt *} or {\tt +}) is bound in the semantics of
the production, e.g. 

{\tt \begin{verbatim}
Disjunction --> Conjunction+ "|" 
                {Disj: [(-terms Conjunction+)]};
     \end{verbatim}
}

builds a structure of type {\tt Disj} with the {\tt -terms} slot
filled by the value of the Kleene-constituent {\tt Conjunction+}.

\paragraph {Example grammar using Kleene * Notation}

{\tt \begin{verbatim}

(:name "mini-la" :grammar "zebu-mg" )

;; Domain definition

Program := [(-stmts kb-sequence)];
Application := [(-function) (-args kb-sequence)];

;; rules

Program --> "begin" Stmt+ ";" "end"
             { Program: [(-stmts Stmt+)] } ;

Stmt    --> Identifier | Appl | Program ;

Appl    --> Identifier "(" Arg* " " ")"
             {Application: [(-function Identifier) (-args Arg*)]};

Arg     --> Identifier | Number | Appl ;
     \end{verbatim}
}

Compiling this grammar generates a parser/unparser (i.e. the printing
routines are generated automatically).

{\tt \begin{verbatim}
(zb:read-parser "begin A; B ; C end"
                :grammar (zb:find-grammar "mini-la"))
     \end{verbatim}
}

returns a structure of type {\tt PROGRAM} which is printed in the
syntax of ``mini-la'':

{\tt \begin{verbatim}
begin A;B;C end
> (describe *)
begin A;B;C end is a structure of type PROGRAM.
It has 1 slot, with the following values:
 -STMTS:                      A;B;C

(describe (PROGRAM--STMTS *))
A;B;C is a structure of type KB-SEQUENCE.
It has 2 slots, with the following values:
 FIRST:                       A
 REST:                        B C
     \end{verbatim}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Using the Compiler} \label{Compiler}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Compiling a grammar}

The {\sf Zebu}-compiler\footnote{For installation see appendix
\ref{installation}.} can be called using any of the following
functions:

\begin{tabbing}
mmmmmmmm\=mmmmmmmmmmmmmmm\=mmmmmmmmmmmmmm\=\kill
{\tt zebu-compile-file}                        \>\>\>{\em function} \\
    \>({\em grammar-file} {\tt \&key} {\em output-file} {\em grammar} {\em verbose})
\end{tabbing}

This compiles the LALR(1) grammar in a file named {\em grammar-file}.
The {\em output-file} defaults to a file with the same name as {\em
grammar-file} but type "{\tt tab}".  The grammar used for compilation
defaults to the null-grammar. If {\em verbose} is {\em true}, conflict
warnings will be printed.  {\tt zebu-compile-file} returns the
pathname of {\em output-file}.

\paragraph {Example:}
{\tt \begin{verbatim}
 (let ((*warn-conflicts* t)
       (*allow-conflicts* t))
   (zebu-compile-file "dangelse.zb" 
                      :output-file "/tmp/dangelse.tab"))

 ; Zebu Compiling (Version 2.0)
 ; "~/zebu/test/dangelse.zb" to "/tmp/dangelse.tab"

 Reading grammar from dangelse.zb

 Start symbols is: S

 4 productions, 8 symbols
 .........9 item sets
 .........
 .........
 ;;; Warning: ACTION CONFLICT!!!-- state: 8
 ;;;          old entry: (6 :S 2)  new entry: (6 :R 2)
 ;;;          
 ;;; Warning: Continuing to build tables despite conflicts...
 ;;;          Will prefer old entry: (6 :S 2)

 Dumping parse tables to /tmp/dangelse.tab
 #P"/tmp/dangelse.tab"
\end{verbatim}}

\begin{tabbing}
mmmmmmmm\=mmmmmmmmmmmmmmm\=mmmmmmmmmmmmmm\=\kill
{\tt *warn-conflicts*}                        \>\>\>{\em variable} 
\end{tabbing}

If {\em true} during LALR-table construction, shift-reduce conflicts
will be reported.  By default, {\tt *warn-conflicts*} is false.

\begin{tabbing}
mmmmmmmm\=mmmmmmmmmmmmmmm\=mmmmmmmmmmmmmm\=\kill
{\tt *allow-conflicts*}                        \>\>\>{\em variable} 
\end{tabbing}

If {\em true} during LALR-table construction, shift-reduce conflicts will be
resolved in favor of the old entry.  By default, {\tt *allow-conflicts*}
is {\em true}.

\begin{tabbing}
mmmmmmmm\=mmmmmmmmmmmmmmm\=mmmmmmmmmmmmmm\=\kill
{\tt *check-actions*}                        \>\>\>{\em variable} 
\end{tabbing}

If {\em true} the semantic action associated with a production will be
compiled at grammar compilation time in order to display possible
warning messages. By default, {\tt *check-actions*} is false.

\begin{tabbing}
mmmmmmmm\=mmmmmmmmmmmmmmm\=mmmmmmmmmmmmmm\=\kill
({\tt compile-slr-grammar} ({\em grammar-file} {\tt \&key} {\em output-file} {\em grammar}) \>\>\>{\em function} 
\end{tabbing}

This is like {\tt zebu-compile-file}, but an SLR-table will be made.  

Example:
{\tt \begin{verbatim}
 (compile-slr-grammar "dangelse.zb" 
     :output-file "/tmp/dangelse.tab")

 Reading grammar from dangelse.zb
 
 Start symbols is: S

 4 productions, 8 symbols
 .........9 item sets

 Dumping parse tables to /tmp/dangelse.tab
 #P"/tmp/dangelse.tab"
     \end{verbatim}}

\begin{tabbing}
mmmmmmmm\=mmmmmmmmmmmmmmm\=mmmmmmmmmmmmmm\=\kill
{\tt compile-lalr1-grammar} ({\em grammar-file} {\tt \&key} {\em output-file} {\em grammar}) \>\>\>{\em function} 
\end{tabbing}


This is like {\tt zebu-compile-file}, but does not expand logical pathnames.

Example:

{\tt \begin{verbatim}
 (compile-lalr1-grammar "dangelse.zb"
                        :output-file "/tmp/dangelse.tab")

 Reading grammar from dangelse.zb

 Start symbols is: S

 4 productions, 8 symbols
 .........9 item sets
 .........
 .........
 Dumping parse tables to /tmp/dangelse.tab
 #P"/tmp/dangelse.tab"
\end{verbatim}}


\subsection{Loading a grammar}

\begin{tabbing}
mmmmmmmm\=mmmmmmmmmmmmmmm\=mmmmmmmmmmmmmm\=\kill
{\tt zebu-load-file} ({\em filename} {\tt \&key} {\em verbose})   \>\>\>{\em function} 
\end{tabbing}

{\em filename} should be the name of a compiled grammar file, i.e. a
file of type "{\tt tab}".  If such a file can be found, it will be
loaded, returning the grammar object needed for parsing.  In case a
domain-file was generated by compiling the grammar, it will also be
loaded.  The type of the domain-file is the first for which a file
exists, by examining the lists
\begin{quote}
{\tt *load-binary-pathname-types*} and\\
{\tt *load-source-pathname-types*}
\end{quote} in turn.

  The keyword argument {\em verbose} defaults to {\em true}.

\paragraph {Example:}
{\tt \begin{verbatim}
 (zebu-load-file "/tmp/dangelse.tab")
 <Zebu Grammar: dangelse>
\end{verbatim}}

It is possible to have many grammars loaded concurrently.  Given the name
of a grammar, one can find a grammar that has been loaded by:

\begin{tabbing}
mmmmmmmm\=mmmmmmmmmmmmmmm\=mmmmmmmmmmmmmm\=\kill
{\tt find-grammar} ({\em name})   \>\>\>{\em function} 
\end{tabbing}


{\em name} must be a string.  If a grammar of the same name (ignoring
case) has been loaded, the grammar object is returned, else {\em
false} is returned.

\paragraph {Example:}
{\tt \begin{verbatim}
 (find-grammar "dangelse")
 <Zebu Grammar: dangelse>
     \end{verbatim}}


\subsection{Parsing a string with a grammar}

\begin{tabbing}
mmmmmmmm\=mmmmmmmmmmmmmmm\=mmmmmmmmmmmmmm\=\kill
{\tt read-parser} \>\>\>{\em function} \\
   \> ({\em string} {\tt \&key} {\em grammar} {\em junk-allowed} {\em
print-parse-errors} {\em error-fn}  {\em start})
\end{tabbing}

The argument of the {\tt :grammar} keyword defaults to {\tt
*current-grammar*} initially is bound to the null-grammar,
e.g.

\begin{tabbing}
mm\=mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm\kill
\> {\tt (read-parser \metavar{{\em string}} :grammar (find-grammar \metavar{{\em name}}))}\\
\\
\> is equivalent to\\
\\
\> {\tt (setq zebu:*current-grammar* (find-grammar \metavar{name}))}\\
\> {\tt (read-parser \metavar{string})}
\end{tabbing}


{\tt read-parser} parses the string starting at the position indicated
by {\tt :start} (default 0).

{\tt read-parser} takes the keyword argument {\tt :junk-allowed},
which if {\em true} will return as second value an index to the
unparsed remainder of the string in case not the entire string was
consumed by the parse.

The keyword {\tt :junk-allowed} has the same meaning as in the {\sf
Common Lisp} function {\tt read-from-string}.

{\tt :print-parse-errors} controls the printing of errors during
parsing and defaults to {\em true}.

{\tt :error-fn} is a function used to report errors, it defaults to
the {\sf Common Lisp} {\tt error} function.

\paragraph{Example:}

\begin{verbatim}
 (read-parser "if f then if g then h else i" 
              :grammar (find-grammar "dangelse"))
 ("if" F "then" ("if" G "then" H "else" I))

 (read-parser "1 + a" :grammar (find-grammar "ex1"))
 (+OP (EXPRESSION (TERM (FACTOR 1)))
      (TERM (FACTOR A)))
\end{verbatim}

\subsection{Parsing from a file with a grammar}

\begin{tabbing}
mmmmmmmm\=mmmmmmmmmmmmmmm\=mmmmmmmmmmmmmm\=\kill
{\tt file-parser} ({\em file} {\tt \&key} {\em grammar} {\em print-parse-errors} {\em verbose}) \>\>\>{\em function} 
\end{tabbing}


{\tt file-parser} parses expressions using the grammar specified by
{\tt :grammar}, reading from {\em file}.  It returns a list of the
parse-results, i.e. what would have been returned by {\tt read-parser}.

The {\tt :grammar} argument defaults to {\tt *current-grammar*} -- which
initially is bound to the ``null-grammar''.

{\tt :print-parse-errors} controls the printing of errors during parsing and
defaults to {\em true}. 

{\tt :verbose} controls whether printing of parse-results occurs, and
defaults to {\em true}.

The processing of comments by {\tt file-parser} can be influenced by
the following variables:
\begin{itemize}
  \item {\tt zb:*comment-brackets*} is a list of bracket pairs. 
   Everything between any of bracket pairs is  ignored.
   Initially {\tt zb:*comment-brackets*} is
            set to \verb+(("#\|" . "|#"))+. 
  \item {\tt zb:*comment-start*}   A line beginning with this
   character is ignored.  Initially {\tt zb:*comment-start*} is set to
   the semicolon character: \verb+#\;+
\end{itemize}

\paragraph{Example:}

{\tt \begin{verbatim}
 (zb:file-parser "sample-ex1" :grammar (zb:find-grammar "ex1"))
 ...
\end{verbatim}}


\subsection{Parsing from a list of tokens}

\begin{tabbing}
mmmmmmmm\=mmmmmmmmmmmmmmm\=mmmmmmmmmmmmmm\=\kill
{\tt list-parser} ({\em token-list} {\tt \&key} {\em grammar} {\em junk-allowed})  \>\>\>{\em function} 
\end{tabbing}

{\tt list-parser} is like {\tt read-parser} except that the tokens
that are passed by the scanner to the driver are already given as the
elements of {\em token-list}.  This function is useful if the options for
controlling lexical analysis given in section \ref{grammar-options}
are insufficient.

\paragraph {Example:}
{\tt \begin{verbatim}
 (let ((*current-grammar* (find-grammar "ex1")))
    (list-parser '(1 "+" x "*" y)))
 (+OP (EXPRESSION (TERM (FACTOR 1)))
      (*-OP (TERM (FACTOR X)) (FACTOR Y)))
     \end{verbatim}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section {Lexical Analysis}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Customization and Regular Expressions}

It should only seldomly be necessary to write a lexical analyser.
Before you write your own lexical analyzer, check whether the
following variables and keywords would suffice to parameterize
lexical analysis:

{\tt \begin{tabbing}
mmmm\=mmmmmmmmmmmmmmmmmmmmmmmmmm\kill
    \>zb:*comment-start*\\
    \>zb:*comment-brackets*\\
    \>zb:*disallow-packages*\\
    \>zb:*preserve-case*\\
    \>zb:*case-sensitive*\\
    \>:case-sensitive\\
    \>:identifier-start-chars\\
    \>:identifier-continue-chars\\
    \>:string-delimiter\\
    \>:symbol-delimiter\\
    \>:white-space \\
    \>:lex-cats \\
\end{tabbing}
}

\subsection{Introducing new Categories by Regular Expressions}
\label{lex-cats}
The keyword {\tt :lex-cats} takes as argument an association list of
the form:
{\tt \begin{tabbing}
mmmm\=mmmmmmmmmmmmmmmmmmmmmmmmmm\kill
 \>((\metavar{Category} \metavar{Regular Expression}) ...)
     \end{tabbing}
}

\metavar{Category} is a symbol naming a lexical category and
\metavar{Regular Expression} is a string representing a regular
expression as defined in the GNU Emacs Lisp Manual \cite{cs:GNULisp}.
The regular expression will be compiled into a Common Lisp function
and invoked by {\tt read-parser} before the built-in categories
(Identifier, String, Number) are examined.  The categories can be used
in rules like any of the built-in categories.

The regular expression compiler\footnote{Thanks to Lawrence E. Freil
who wrote the main part of the Regular Expression Compiler.} handles the
following constructs:

\begin{description}

\item[.] Period matches any single character except a newline.
\item[*] repeats preceding regular expression as many times as possible.
\item[+] like * but must match at least once.
\item[?] like * but must match once or not at all.
\item[{[\ldots]}] '[' begins a character set, which is terminated by ']'.\\
              Character ranges can be indicated, e.g. a-z, 0-9.
\item[{[ $\hat{}$ \ldots]}] forms the complement character set.
\item[\$] matches only at the end of a line.
\item[$\backslash$(... $\backslash$)] is a grouping construct.
\item[$\backslash$ \metavar{digit}] means: accept the same string as was matched
        by the group in position \metavar{digit}.
\end{description}

\paragraph {Example:}

{\tt \begin{verbatim}
 :lex-cats ((BibTeX-in-braces "{[^\\n}]*}"))
 \end{verbatim}}

defines a new category {\tt BibTeX-in-braces} which matches anything
starting with ``\{'', ending in ``\}'', and not containing either a
newline or ``\}''.


{\tt \begin{verbatim}
 :lex-cats ((Ratio_Number "-?[0-9]+/[0-9]+")
	    (Simple_Float "-?[0-9]*\\.[0-9]+"))
 \end{verbatim}}

defines the syntax for rationals and floating point numbers.  Note
that the period needs to be escaped, since it is a special character of
the regular expression language.

\subsection{The functional interface to the parsing engine}

In case the above parameterization facilities for lexical analysis are
insufficient or you want to use an existing lexical analyzer, you need
to understand the functional interface to the parsing engine as
implemented by the {\tt lr-parse}.


\begin{tabbing}
mmmmmmmm\=mmmmmmmmmmmmmmm\=mmmmmmmmmmmmmm\=\kill {\tt lr-parse}
\>\>\>{\em function} \\ mm\=mmmmmmmmmmmmmm\kill \> ({\em next-sym-fn}
{\em error-fn} {\em grammar} {\tt \&optional} {\em junk-allowed} {\em
last-pos-fn})
\end{tabbing}

{\tt lr-parse} returns the result of parsing the token stream produced
by {\em error-fn} with {\em grammar} by the LALR(1) method.  In case
{\em junk-allowed} is {\em true} it produces as second value a handle
to the yet unconsumed token stream by calling the function {\em
last-pos-fn}.

{\em next-sym-fn} should be bound to a generator function --- a
function of no arguments --- that will be called to produce the next
token.  It should return two values: (1) the token found and (2) the
category of the token (obtained by the function {\tt categorize}. 

{\em error-fn} is the function to be called in case of an error.  {\em
grammar} is the grammar object that contains important information for
lexical analysis, (e.g. the table of keywords).  

To understand the interface to {\tt lr-parse}, consider how
{\tt list-parser} (described above) might have been defined:

{\tt \begin{verbatim}
(defun list-parser (token-list &key (grammar *current-grammar*)
                                    junk-allowed)
  (let ((last-position token-list)
        token1)
    (check-type token-list list)
    (lr-parse
     ;; The LEXER supplied to the parsing engine:
     #'(lambda ()
         (if (null token-list)
             (end-of-tokens-category grammar)
           (progn
             (setq last-position token-list
                   token1 (pop token-list))
             (categorize token1 grammar))))
     ;; The error function supplied to the parsing engine:
     #'(lambda (string)
         (error "~S~% Remaining tokens: ~S~{ ~S~}"
                string token1 token-list))
     grammar
     junk-allowed
     ;; Function that returns the remaining unparsed token-list
     #'(lambda () last-position))))
     \end{verbatim}
}

\begin{tabbing}
mmmmmmmm\=mmmmmmmmmmmmmmm\=mmmmmmmmmmmmmm\=\kill
{\tt end-of-tokens-category} ({\em grammar}) \>\>\>{\em function} 
\end{tabbing}

{\tt end-of-tokens-category} returns two values: a token signifying
the end of the token stream and the appropriate lexical category.


\begin{tabbing}
mmmmmmmm\=mmmmmmmmmmmmmmm\=mmmmmmmmmmmmmm\=\kill
{\tt categorize} ({\em token} {\em grammar})  \>\>\>{\em function} 
\end{tabbing}
{\tt categorize} returns the {\em token} itself and its category, a
number that represents one of {\tt number}, {\tt identifier}, {\tt
string} or a particular terminal token of the grammar.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section {Future Work}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Translation involves three processes:
\begin{itemize}
  \item parsing
  \item transformation
  \item generation
\end{itemize}

 {\sf Zebu} is a tool that helps in 1 and 3. There are cases where 2
reduces to the identity function, since the abstract syntax is the
same for the source and the target language of translation.  Examples
for these ``syntactic variants'' are infix and prefix notation for
arithmetic or boolean expressions.

 In general, the situation is more complicated.  For languages with
the same expressive power, some transformation process can be defined.
Between languages with different expressive power such a
transformation is not always possible.  For a language that is not
Turing complete, it is not possible to express every computation, e.g.
SQL cannot express rcursion, and hence it is not possible to express
the ``ancestor'' relation (which is recursively defined).  A technique
to represent transformation are ``rewrite rule systems''.  The Refine
language contains a rewrite-rule mechanism in which the rules are in
terms of patterns of the concrete syntax.  We have implemented a
rewrite-rule system based on typed feature structures, called {\sf
Zebu-RR}, which will be described in a future report.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%                                  Appendix
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\appendix 

\section{Installation}
\label{installation}

There are two ways to install {\sf Zebu}:

\begin{itemize}
  \item  Installation using {\tt defsystem}

This makes it easier to load and compile grammars, since one does not
need to remember the location of a module in a directory structure and
the particular compilation and loading functions.  To install, follow
the directions in {\tt ZEBU-sys.l}.  You need the portable {\tt
defsys} for that.  This is available as {\tt Defsys.tar.Z} at the same
place as {\tt zebu-???.tar.Z}.

The file {\tt ZEBU-sys.l} is used to load or compile {\sf Zebu}, which
actually consists of two systems (defined by {\tt defsystem})

\begin{tabbing}
mmmmm\=mmmmmmmmmmmmmmm\=mmmmmmmmmmmmmm\=\kill
     \>{\sf Zebu}           \>the runtime system\\
     \>{\sf Zebu-compiler}  \>the compiler\\
\end{tabbing}

  \item  Installation without {\tt defsystem}\\
If you don't want to use {\tt defsystem}, load the file {\tt
COMPILE-ZEBU.l}, which compiles the {\sf Zebu} files in the right
order.

After loading the file {\tt ZEBU-init.l} you can call:

       {\tt (zb:zebu)}                to load the runtime system\\
or\\
       {\tt (zb:zebu-compiler)}       to load the grammar compiler.
\end{itemize}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\bibliography{/users/laubsch/texlib/general}
\begin{thebibliography}{99}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\bibitem{aho:79}
A.V. Aho and J.D. Ullman.
\newblock {\em Principles of Compiler Design}.
\newblock Addison Wesley, New York, 1979.

\bibitem{compiler:88}
Charles~N. Fischer and Richard~J. LeBlanc.
\newblock {\em Crafting a Compiler}.
\newblock Benjamin/Cummings, Menlo Park, CA, 1988.

\bibitem{cs:Genesereth92}
Michael~R. Genesereth.
\newblock An agent-based framework for software interoperability.
\newblock Technical Report Logic-92-02, Departmentof Computer Science, Stanford
  University, Stanford, 1992.

\bibitem{cs:kif92}
Michael~R. Genesereth, Richard Fikes, et~al.
\newblock Knowledge interchange format, version 3.0. reference manual.
\newblock Report Logic-92-1, Logic Group Report, Computer Science Department,
  Stanford University, Stanford, June 1992.

\bibitem{johnson:88}
Mark Johnson.
\newblock {\em Attribute Value Logic and the Theory of Grammar}.
\newblock Center for the Study of Language and Information, Stanford, 1988.

\bibitem{ap:refine}
Joachim Laubsch and Derek Proudian.
\newblock A case study in {REFINE}: interfacing modules via languages.
\newblock Report HPL-STL-TM-88-11, Hewlett Packard, 1988.

\bibitem{cs:GNULisp}
Bill Lewis, Dan LaLiberte, and the GNU Manual~Group.
\newblock {\em GNU Emacs Lisp Reference Manual}.
\newblock The Free Software Foundation, Cambridge, MA, December 1990.

\bibitem{refine}
Reasoning Systems, Palo Alto, 3260 Hillview Ave., CA 94304.
\newblock {\em Refine User's Guide}, 1989.

\bibitem{ap:smith85}
Douglas~R. Smith, Gordon~B. Kotik, and Stephen~J. Westfold.
\newblock Research on knowledge-based software environments at {KESTREL}
  institute.
\newblock {\em IEEE Transactions on Software Engineering}, SE-11:1278--1295,
  November 1985.

\end{thebibliography}

\newpage
\tableofcontents\contentsline {paragraph}{Keywords}{1}

\end{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%                            End of Zebu_intro.tex
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
